{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Valid Permutations for DI Sequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numPermsDISequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #DI 序列的有效排列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个长度为 <code>n</code> 的字符串 <code>s</code> ，其中 <code>s[i]</code> 是:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>“D”</code> 意味着减少，或者</li>\n",
    "\t<li><code>“I”</code> 意味着增加</li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>有效排列</strong>&nbsp;是对有&nbsp;<code>n + 1</code>&nbsp;个在&nbsp;<code>[0, n]</code>&nbsp; 范围内的整数的一个排列&nbsp;<code>perm</code>&nbsp;，使得对所有的&nbsp;<code>i</code>：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果 <code>s[i] == 'D'</code>，那么&nbsp;<code>perm[i] &gt; perm[i+1]</code>，以及；</li>\n",
    "\t<li>如果 <code>s[i] == 'I'</code>，那么 <code>perm[i] &lt; perm[i+1]</code>。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回 <em><strong>有效排列 </strong>&nbsp;</em><code>perm</code><em>的数量 </em>。因为答案可能很大，所以请<strong>返回你的答案对</strong>&nbsp;<code>10<sup>9</sup>&nbsp;+ 7</code><strong>&nbsp;取余</strong>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"DID\"\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>\n",
    "(0, 1, 2, 3) 的五个有效排列是：\n",
    "(1, 0, 3, 2)\n",
    "(2, 0, 3, 1)\n",
    "(2, 1, 3, 0)\n",
    "(3, 0, 2, 1)\n",
    "(3, 1, 2, 0)\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> s = \"D\"\n",
    "<strong>输出:</strong> 1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == s.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 200</code></li>\n",
    "\t<li><code>s[i]</code>&nbsp;不是&nbsp;<code>'I'</code>&nbsp;就是&nbsp;<code>'D'</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [valid-permutations-for-di-sequence](https://leetcode.cn/problems/valid-permutations-for-di-sequence/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [valid-permutations-for-di-sequence](https://leetcode.cn/problems/valid-permutations-for-di-sequence/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"DID\"', '\"D\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPermsDISequence(self, s: str) -> int:\n",
    "        MOD = 1000000007\n",
    "        n = len(s)\n",
    "        memo = [0]*(n+1)\n",
    "        memo[0] = 1\n",
    "        for i in range(1, n+1):\n",
    "            next_memo = [0]*(n+1)\n",
    "            if s[i-1] == 'I':\n",
    "                for j in range(i+1):\n",
    "                    next_memo[j] = sum(memo[k] for k in range(j))\n",
    "                    next_memo[j] %= MOD\n",
    "            else:\n",
    "                for j in range(i):\n",
    "                    next_memo[j] = sum(memo[k] for k in range(j, i))\n",
    "                    next_memo[j] %= MOD\n",
    "            memo = next_memo\n",
    "        return sum(memo) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPermsDISequence(self, s: str) -> int:\n",
    "        n = len(s) \n",
    "        dp = [1] * (n + 1)\n",
    "        for i in range(n):\n",
    "            new = [0] * (n + 1)\n",
    "            for cur in range(n + 1):\n",
    "                if s[i] == 'D':\n",
    "                    for pre in range(cur, i + 1):\n",
    "                        new[cur] += dp[pre]\n",
    "                        new[cur] %= 10 ** 9 + 7 \n",
    "                else:\n",
    "                    for pre in range(cur):\n",
    "                        new[cur] += dp[pre]\n",
    "                        new[cur] %= 10 ** 9 + 7 \n",
    "            dp = new \n",
    "        return sum(dp) % (10 ** 9 + 7)\n",
    "\n",
    "\n",
    "        n = len(s)\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[0] = 1\n",
    "        for i in range(n):\n",
    "            new = [0] * (n + 1)\n",
    "            for cur in range(n + 1):\n",
    "                if s[i] == 'D':\n",
    "                    for pre in range(cur, i + 1):\n",
    "                        new[cur] += dp[pre]\n",
    "                        new[cur] %= 10 ** 9 + 7\n",
    "                else:\n",
    "                    for pre in range(cur):\n",
    "                        new[cur] += dp[pre]\n",
    "                        new[cur] %= 10 ** 9 + 7\n",
    "            dp = new \n",
    "        return sum(dp) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def numPermsDISequence(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = [[0] * (n + 1) for _ in range(2)]\n",
    "        presum = [0, 1]\n",
    "        for i in range(1, n + 1):\n",
    "            tmp = [0]\n",
    "            for j in range(i + 1):\n",
    "                f[i & 1][j] = (presum[i] - presum[j] if s[i - 1] == \"D\" else presum[j]) % MOD\n",
    "                tmp.append(tmp[-1] + f[i & 1][j])\n",
    "            presum = tmp\n",
    "        return presum[-1] % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPermsDISequence(self, s: str) -> int:\n",
    "        n = len(s) \n",
    "        dp = [1] * (n + 1)\n",
    "        for i in range(n):\n",
    "            new = [0] * (n + 1)\n",
    "            for cur in range(n + 1):\n",
    "                if s[i] == 'D':\n",
    "                    for pre in range(cur, i + 1):\n",
    "                        new[cur] += dp[pre]\n",
    "                        new[cur] %= 10 ** 9 + 7 \n",
    "                else:\n",
    "                    for pre in range(cur):\n",
    "                        new[cur] += dp[pre]\n",
    "                        new[cur] %= 10 ** 9 + 7 \n",
    "            dp = new \n",
    "        return sum(dp) % (10 ** 9 + 7)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numPermsDISequence(self, s: str) -> int:\r\n",
    "\r\n",
    "        # answer 1\r\n",
    "        # ans = 0\r\n",
    "        # mod = 1e9+7\r\n",
    "        # n = len(s)\r\n",
    "        # # 符合序列[0,i]并且以j结尾的个数,0<=j<=i,难点在于以j结尾就要求前面不能出现J\r\n",
    "        # f = [[0]*(n+1) for _ in range(n+1)]\r\n",
    "        # f[0][0] = 1\r\n",
    "        # for i in range(1, n+1):\r\n",
    "        #     if s[i-1] == 'D':\r\n",
    "        #         f[i][i] = 0\r\n",
    "        #         for j in reversed(range(i)):\r\n",
    "        #             f[i][j] = (f[i][j+1]+f[i-1][j]) % mod\r\n",
    "        #     elif s[i-1] == 'I':\r\n",
    "        #         f[i][0] = 0\r\n",
    "        #         for j in range(1, i+1):\r\n",
    "        #             f[i][j] = (f[i][j-1]+f[i-1][j-1]) % mod\r\n",
    "        # for j in range(n+1):\r\n",
    "        #     ans = (ans + f[n][j]) % mod\r\n",
    "        # return int(ans)\r\n",
    "\r\n",
    "        # answer 2\r\n",
    "        ans = 0\r\n",
    "        mod = 1e9+7\r\n",
    "        n = len(s)\r\n",
    "        f = [[0]*(n+1)for _ in range(n+1)]\r\n",
    "        for i in range(n+1):\r\n",
    "            f[0][i] = 1\r\n",
    "        for i in range(1, n+1):\r\n",
    "            if s[i-1] == 'D':\r\n",
    "                for j in reversed(range(n+1-i)):\r\n",
    "                    f[i][j] = (f[i][j+1]+f[i-1][j+1]) % mod\r\n",
    "            elif s[i-1] == 'I':\r\n",
    "                for j in range(n+1-i):\r\n",
    "                    f[i][j] = (f[i][j-1]+f[i-1][j]) % mod\r\n",
    "\r\n",
    "        return int(f[n][0])\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "md = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def numPermsDISequence(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        dp = [[0] * (n+1) for _ in range(1+n)]\n",
    "\n",
    "        dp[0][0]=1\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            if s[i-1] == 'D':\n",
    "                dp[i][i]=0\n",
    "                for j in range(i-1, -1, -1):\n",
    "                    dp[i][j] = (dp[i][j+1] + dp[i-1][j]) % md\n",
    "\n",
    "            else:\n",
    "                dp[i][0] = 0\n",
    "                for j in range(1, i+1):\n",
    "                    dp[i][j] = (dp[i][j-1] + dp[i-1][j-1]) % md\n",
    "        res = 0\n",
    "        for i in range(n+1):\n",
    "            res = (res + dp[n][i]) % md\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPermsDISequence(self, S: str) -> int:\n",
    "        l=len(S)\n",
    "        dp=[[0  for _ in range(l+1)] for _ in range(l+1)]\n",
    "        dp[0][0]=1\n",
    "        for i in range(1,l+1):\n",
    "            for j in range(i+1):\n",
    "                if S[i-1]=='D':\n",
    "                    for k in range(j,i):\n",
    "                        dp[i][j]=(dp[i][j]+dp[i-1][k])%1000000007\n",
    "                else:\n",
    "                    for k in range(0,j):\n",
    "                        dp[i][j]=(dp[i][j]+dp[i-1][k])%1000000007\n",
    "        res=0\n",
    "        for i in range(l+1):\n",
    "            res=(res+dp[l][i])%1000000007\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def numPermsDISequence(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        f[0][0] = 1\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            if s[i - 1] == 'D':\n",
    "                for j in range(i - 1, -1, -1):\n",
    "                    f[i][j] = (f[i - 1][j] + f[i][j + 1]) % MOD\n",
    "            else:\n",
    "                for j in range(1, i + 1):\n",
    "                    f[i][j] = (f[i - 1][j - 1] + f[i][j - 1]) % MOD\n",
    "        res = 0\n",
    "        for i in range(n + 1):\n",
    "            res += f[n][i]\n",
    "            res %= MOD\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numPermsDISequence(self, s: str) -> int:\r\n",
    "        sz=len(s)\r\n",
    "        f=[[0]*(sz+1) for _ in range(sz+1)]\r\n",
    "        f[0][0]=1\r\n",
    "        Mod=10**9+7\r\n",
    "        for i in range(1,sz+1):\r\n",
    "            if s[i-1]=='D':\r\n",
    "                f[i][i]=0\r\n",
    "                for j in range(i-1,-1,-1):\r\n",
    "                    f[i][j]=(f[i][j+1]+f[i-1][j])%Mod\r\n",
    "            else:\r\n",
    "                f[i][0]=0\r\n",
    "                for j in range(1,i+1):\r\n",
    "                    f[i][j]=(f[i][j-1]+f[i-1][j-1])%Mod\r\n",
    "        return sum(f[-1])%Mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numPermsDISequence(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(s)\n",
    "        dp = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            if s[i - 1] == \"D\":\n",
    "                for j in range(i - 1, -1, -1):\n",
    "                    dp[i][j] = (dp[i][j] + dp[i][j + 1] + dp[i - 1][j]) % MOD\n",
    "            else:\n",
    "                for j in range(1, i + 1):\n",
    "                    dp[i][j] = (dp[i][j] + dp[i][j - 1] + dp[i - 1][j - 1]) % MOD\n",
    "\n",
    "        res = 0\n",
    "        for j in range(n + 1):\n",
    "            res = (res + dp[n][j]) % MOD\n",
    "        return res\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def numPermsDISequence(self, s: str) -> int:\n",
    "#         MOD = 10 ** 9 + 7\n",
    "#         n = len(s)\n",
    "#         dp = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "#         dp[0][0] = 1\n",
    "#         for i in range(1, n + 1):\n",
    "#             for j in range(i + 1):\n",
    "#                 if s[i - 1] == \"D\":\n",
    "#                     for k in range(j, i):\n",
    "#                         dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD\n",
    "#                 else:\n",
    "#                     for k in range(0, j):\n",
    "#                         dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD\n",
    "#         res = 0\n",
    "#         for j in range(n + 1):\n",
    "#             res = (res + dp[n][j]) % MOD\n",
    "#         return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPermsDISequence(self, s: str) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        n = len(s)\n",
    "\n",
    "        dp = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            if s[i - 1] == 'D':\n",
    "                dp[i][i] = 0\n",
    "                for j in range(i - 1, -1, -1):\n",
    "                    dp[i][j] = (dp[i][j + 1] + dp[i - 1][j]) % MOD\n",
    "            else:\n",
    "                dp[i][0] = 0\n",
    "                for j in range(1, i + 1):\n",
    "                    dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - 1]) % MOD\n",
    "\n",
    "        res = 0\n",
    "        for j in range(0, n + 1):\n",
    "            res = (res + dp[n][j]) % MOD\n",
    "\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numPermsDISequence(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(s)\n",
    "        dp = [[0] * (n + 2) for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            if s[i - 1] == \"D\":\n",
    "                for j in range(i - 1, -1, -1):\n",
    "                    dp[i][j] = (dp[i][j] + dp[i][j + 1] + dp[i - 1][j]) % MOD\n",
    "            else:\n",
    "                for j in range(1, i + 1):\n",
    "                    dp[i][j] = (dp[i][j] + dp[i][j - 1] + dp[i - 1][j - 1]) % MOD\n",
    "\n",
    "        res = 0\n",
    "        for j in range(n + 1):\n",
    "            res = (res + dp[n][j]) % MOD\n",
    "        return res\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def numPermsDISequence(self, s: str) -> int:\n",
    "#         MOD = 10 ** 9 + 7\n",
    "#         n = len(s)\n",
    "#         dp = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "#         dp[0][0] = 1\n",
    "#         for i in range(1, n + 1):\n",
    "#             for j in range(i + 1):\n",
    "#                 if s[i - 1] == \"D\":\n",
    "#                     for k in range(j, i):\n",
    "#                         dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD\n",
    "#                 else:\n",
    "#                     for k in range(0, j):\n",
    "#                         dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD\n",
    "#         res = 0\n",
    "#         for j in range(n + 1):\n",
    "#             res = (res + dp[n][j]) % MOD\n",
    "#         return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPermsDISequence(self, s: str) -> int:\n",
    "        N = len(s)\n",
    "        dp = [[0] * (N + 1) for _ in range(N + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, N + 1):\n",
    "            for j in range(i + 1):\n",
    "                if s[i - 1] == 'D':\n",
    "                    dp[i][j] = sum(dp[i - 1][k] for k in range(j, i)) % (10 ** 9 + 7)\n",
    "                else:\n",
    "                    dp[i][j] = sum(dp[i - 1][k] for k in range(j)) % (10 ** 9 + 7)\n",
    "        return sum(dp[N]) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numPermsDISequence(self, s: str) -> int:\r\n",
    "        ans = 0\r\n",
    "        mod = 1e9+7\r\n",
    "        n = len(s)\r\n",
    "        # 符合序列[0,i]并且以j结尾的个数,0<=j<=i,难点在于以j结尾就要求前面不能出现J\r\n",
    "        f = [[0]*(n+1) for _ in range(n+1)]\r\n",
    "        f[0][0] = 1\r\n",
    "        for i in range(1, n+1):\r\n",
    "            if s[i-1] == 'D':\r\n",
    "                f[i][i] = 0\r\n",
    "                for j in reversed(range(i)):\r\n",
    "                    f[i][j] = (f[i][j+1]+f[i-1][j]) % mod\r\n",
    "            elif s[i-1] == 'I':\r\n",
    "                f[i][0] = 0\r\n",
    "                for j in range(1, i+1):\r\n",
    "                    f[i][j] = (f[i][j-1]+f[i-1][j-1]) % mod\r\n",
    "        for j in range(n+1):\r\n",
    "            ans = (ans + f[n][j]) % mod\r\n",
    "        return int(ans)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPermsDISequence(self, s: str) -> int:\n",
    "        dp = [[0] * (len(s) + 1) for _ in range(len(s) + 1)]\n",
    "        for i in range(len(s) + 1):\n",
    "            dp[0][i] = 1\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == 'D':\n",
    "                cnt = 0\n",
    "                # \n",
    "                for j in range(len(s) - i - 1, -1, -1):\n",
    "                    cnt += dp[i][j + 1]\n",
    "                    dp[i + 1][j] = cnt                    \n",
    "            else:\n",
    "                cnt = 0\n",
    "                for j in range(0, len(s) - i):\n",
    "                    cnt += dp[i][j]\n",
    "                    dp[i + 1][j] = cnt\n",
    "        return sum(dp[len(s)]) % int(10 ** 9 + 7)                    \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPermsDISequence(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(s)\n",
    "        dp = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(i + 1):\n",
    "                if s[i - 1] == \"D\":\n",
    "                    for k in range(j, i):\n",
    "                        dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD\n",
    "                else:\n",
    "                    for k in range(0, j):\n",
    "                        dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD\n",
    "\n",
    "        res = 0\n",
    "        for j in range(n + 1):\n",
    "            res = (res + dp[n][j]) % MOD\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def numPermsDISequence(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        f[0][0] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            if s[i - 1] == 'D':\n",
    "                for j in range(i - 1, -1, -1):\n",
    "                    f[i][j] = (f[i - 1][j] + f[i][j + 1]) % MOD\n",
    "            else:\n",
    "                for j in range(1, i + 1):\n",
    "                    f[i][j] = (f[i - 1][j - 1] + f[i][j - 1]) % MOD\n",
    "\n",
    "        res = 0 \n",
    "        for i in range(n + 1):\n",
    "            res += f[n][i]\n",
    "            res %= MOD\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def numPermsDISequence(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        f[0][0] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            if s[i - 1] == 'D':\n",
    "                for j in range(i - 1, -1, -1):\n",
    "                    f[i][j] = (f[i - 1][j] + f[i][j + 1]) % MOD\n",
    "            else:\n",
    "                for j in range(1, i + 1):\n",
    "                    f[i][j] = (f[i][j - 1] + f[i - 1][j - 1]) % MOD\n",
    "        res = 0\n",
    "        for i in range(n + 1):\n",
    "            res += f[n][i]\n",
    "            res %= MOD\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPermsDISequence(self, S):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(S)\n",
    "        dp = [[0 for _ in range(n+1)] for _ in range(n+1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(i + 1):\n",
    "                if S[i - 1] == 'D':\n",
    "                    for k in range(j, i + 1):\n",
    "                        # here start from j, regard as swap value j with i, then shift all values no larger than j\n",
    "                        dp[i][j] += dp[i - 1][k]\n",
    "                        dp[i][j] %= mod\n",
    "                else:\n",
    "                    for k in range(0, j):\n",
    "                        dp[i][j] += dp[i - 1][k]\n",
    "                        dp[i][j] %= mod\n",
    "        #print(dp)\n",
    "        return sum(dp[n]) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPermsDISequence(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 +7\n",
    "        dp = [[0]*(len(s)+1) for _ in range(len(s)+1)]\n",
    "        dp[0] = [1] * (len(s) +1)\n",
    "        for i in range(len(s)):\n",
    "            cur = 0\n",
    "            if s[i] == 'I':\n",
    "                for j in range(len(s) - i):\n",
    "                    dp[i+1][j] = cur = (cur+dp[i][j]) % MOD\n",
    "            else:\n",
    "                for j in range(len(s) - i - 1, -1, -1):\n",
    "                    dp[i+1][j] = cur = (cur + dp[i][j+1]) % MOD\n",
    "        return dp[len(s)][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPermsDISequence(self, s: str) -> int:\n",
    "        self.mod = 10 ** 9 + 7\n",
    "        self.mem = {}\n",
    "        self.dp = [1]\n",
    "        for i in range(1, len(s) + 1):\n",
    "            self.dp.append(self.dp[i - 1] * i)\n",
    "        return self.helper(s) % self.mod\n",
    "    # 相当于每次选最大的数\n",
    "    def helper(self, s):\n",
    "        if not s:\n",
    "            return 1\n",
    "        if s in self.mem:\n",
    "            return self.mem[s]\n",
    "        res = 0\n",
    "        # 可以放开始\n",
    "        if s[0] == 'D':\n",
    "            tmp = self.helper(s[1:])\n",
    "            res += tmp\n",
    "        # 可以放结尾\n",
    "        if s[-1] == 'I':\n",
    "            res += self.helper(s[:-1])\n",
    "        for k in range(len(s) - 1):\n",
    "            # 可以放中间\n",
    "            if s[k] == 'I' and s[k + 1] == 'D':\n",
    "                left = self.helper(s[:k])\n",
    "                right = self.helper(s[k+2:])\n",
    "                res += left * right * self.nCk(len(s), k + 1)\n",
    "        self.mem[s] = res\n",
    "        return res\n",
    "    def nCk(self, n, k):\n",
    "        return (self.dp[n] // self.dp[n - k] // self.dp[k]) % self.mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "我们同样可以使用分治算法（实际上是一种区间动态规划）解决这道题目。\n",
    "首先我们考虑将 0 放在哪里，可以发现 0 要么放在 DI 对应的位置，\n",
    "要么放在排列的开头且对应的字符为 I，要么放在排列的结尾且对应的字符为 D。将 0 放好后，\n",
    "排列被分成了 0 左侧和右侧两部分，每个部分各是一个对应长度的有效排列问题。\n",
    "\n",
    "设左侧的长度为 x，排列的方案数为 f(x)，右侧的长度为 y，排列的方案数为 f(y)，\n",
    "在合并时，我们需要在 x + y 中选择 x 个数分给左侧，剩余的 y 个数分给右侧，\n",
    "因此合并后的方案数为 binom(x + y, x) * f(x) * f(y)，其中 binom 为组合数。\n",
    "'''\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def numPermsDISequence(self, S: str) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "\n",
    "        fac = [1, 1]\n",
    "        for x in range(2, 201):\n",
    "            fac.append(fac[-1] * x % MOD)\n",
    "        facinv = [pow(f, MOD-2, MOD) for f in fac]\n",
    "\n",
    "        def binom(n, k):\n",
    "            return fac[n] * facinv[n-k] % MOD * facinv[k] % MOD\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(i, j):\n",
    "            if i >= j: return 1\n",
    "            ans = 0\n",
    "            n = j - i + 2\n",
    "            if S[i] == 'I': ans += dp(i+1, j)\n",
    "            if S[j] == 'D': ans += dp(i, j-1)\n",
    "\n",
    "            for k in range(i+1, j+1):\n",
    "                if S[k-1:k+1] == 'DI':\n",
    "                    ans += binom(n-1, k-i) * dp(i, k-2) % MOD * dp(k+1, j) % MOD\n",
    "                    ans %= MOD\n",
    "            return ans\n",
    "\n",
    "        return dp(0, len(S) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def numPermsDISequence(self, S):\n",
    "        MOD = 10**9 + 7\n",
    "\n",
    "        fac = [1, 1]\n",
    "        for x in range(2, 201):\n",
    "            fac.append(fac[-1] * x % MOD)\n",
    "        facinv = [pow(f, MOD-2, MOD) for f in fac]\n",
    "\n",
    "        def binom(n, k):\n",
    "            return fac[n] * facinv[n-k] % MOD * facinv[k] % MOD\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(i, j):\n",
    "            if i >= j: return 1\n",
    "            ans = 0\n",
    "            n = j - i + 2\n",
    "            if S[i] == 'I': ans += dp(i+1, j)\n",
    "            if S[j] == 'D': ans += dp(i, j-1)\n",
    "\n",
    "            for k in range(i+1, j+1):\n",
    "                if S[k-1:k+1] == 'DI':\n",
    "                    ans += binom(n-1, k-i) * dp(i, k-2) % MOD * dp(k+1, j) % MOD\n",
    "                    ans %= MOD\n",
    "            return ans\n",
    "\n",
    "        return dp(0, len(S) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPermsDISequence(self, s: str) -> int:\n",
    "        @cache\n",
    "        def dfs(l, r):\n",
    "            if l >= r:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            for i in range(l, r + 1):\n",
    "                h1 = True\n",
    "                if i > l: h1 = s[i - 1] == 'I'\n",
    "                h2 = True\n",
    "                if i < r: h2 = s[i] == 'D'\n",
    "                if h1 and h2:\n",
    "                    ans += dfs(l, i - 1) * dfs(i + 1, r) * math.comb(r - l, (i - 1) - l + 1)\n",
    "                    #print(i)\n",
    "                    ans %= int(1e9 + 7)\n",
    "            #print(l, r, ans)\n",
    "            return ans\n",
    "        return dfs(0, len(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPermsDISequence(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        Mod = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == 0:\n",
    "                return 1\n",
    "            res = 0\n",
    "            if s[i - 1] == \"D\":\n",
    "                res += sum(dfs(i - 1, k) for k in range(j, i))\n",
    "            else:\n",
    "                res += sum(dfs(i - 1, k) for k in range(j))\n",
    "            return res % Mod\n",
    "        return sum(dfs(n, k) for k in range(n + 1)) % Mod\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 1_000_000_007\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numPermsDISequence(self, s: str) -> int:\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i == 0:\n",
    "                return 1\n",
    "            elif s[i - 1] == 'D':\n",
    "                return sum(dfs(i - 1, k) for k in range(j, i)) % MOD\n",
    "            else:\n",
    "                return sum(dfs(i - 1, k) for k in range(j)) % MOD\n",
    "\n",
    "        n = len(s)\n",
    "\n",
    "        res = 0\n",
    "        for j in range(n + 1):\n",
    "            res = (res + dfs(n, j)) % MOD\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def numPermsDISequence(self, S):\n",
    "        MOD = 10**9 + 7\n",
    "        N = len(S)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(i, j):\n",
    "            # How many ways to place P_i with relative rank j?\n",
    "            if i == 0:\n",
    "                return 1\n",
    "            elif S[i-1] == 'D':\n",
    "                return sum(dp(i-1, k) for k in range(j, i)) % MOD\n",
    "            else:\n",
    "                return sum(dp(i-1, k) for k in range(j)) % MOD\n",
    "\n",
    "        return sum(dp(N, j) for j in range(N+1)) % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "动态规划\n",
    "当我们已经确定了排列中的前 i 个元素 P[0], P[1], ..., P[i - 1] 时，\n",
    "我们需要通过字符串 S 的第 i - 1 位 S[i - 1] 和 P[i - 1] 共同确定下一个元素 P[i]。\n",
    "这说明，P[i - 1] 之前的元素 P[0], P[1], .., P[i - 2] 都是无意义的，\n",
    "有意义的是 P[i - 1] 和剩下未选出的 n + 1 - i 个元素的相对大小。\n",
    "例如当 n 的值为 5 时，我们已经确定的排列为 2, 3, 4，未选择的元素为 0, 1, 5，\n",
    "那么有意义的状态是排列 ?, ?, 2 以及未选择的元素 0, 1, 3，\n",
    "其中 ? 表示我们不关心的元素，0, 1, 2, 3 表示 P[i - 1] 和未选择元素的相对大小。\n",
    "\n",
    "这样我们就可以用动态规划解决这道题目。\n",
    "我们用 dp(i, j) 表示确定了排列中到 P[i] 为止的前 i + 1 个元素，\n",
    "并且 P[i] 和未选择元素的相对大小为 j 的方案数（即未选择的元素中，有 j 个元素比 P[i] 小）。\n",
    "在状态转移时，dp(i, j) 会从 dp(i - 1, k) 转移而来，其中 k 代表了 P[i - 1] 的相对大小。\n",
    "如果 S[i - 1] 为 D，那么 k 不比 j 小；如果 S[i - 1] 为 I，那么 k 必须比 j 小。\n",
    "'''\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def numPermsDISequence(self, S: str) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        N = len(S)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(i, j):\n",
    "            # How many ways to place P_i with relative rank j?\n",
    "            if i == 0:\n",
    "                return 1\n",
    "            elif S[i-1] == 'D':\n",
    "                return sum(dp(i-1, k) for k in range(j, i)) % MOD\n",
    "            else:\n",
    "                return sum(dp(i-1, k) for k in range(j)) % MOD\n",
    "\n",
    "        return sum(dp(N, j) for j in range(N+1)) % MOD\n",
    "\n",
    "    '''\n",
    "    我们发现，在上面动态规划的状态转移中，当 S[i - 1] 为 I 时，\n",
    "    dp(i, j) 比 dp(i, j - 1) 多出了 dp(i - 1, j - 1) 这一项；\n",
    "    当 S[i - 1] 为 D 时，dp(i, j) 比 dp(i, j + 1) 多出了 dp(i - 1, j) 这一项，\n",
    "    因此可以不用 dp(i, j) 都计算一遍对应的 dp(i - 1, k) 的和，而是用\n",
    "    dp(i, j) = dp(i, j - 1) + dp(i - 1, j - 1)  if S[i - 1] == 'I'\n",
    "    dp(i, j) = dp(i, j + 1) + dp(i - 1, j)      if S[i - 1] == 'D'\n",
    "    '''\n",
    "    def numPermsDISequence2(self, S: str) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        N = len(S)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(i, j):\n",
    "            # How many ways to place P_i with relative rank j?\n",
    "            if not(0 <= j <= i):\n",
    "                return 0\n",
    "            if i == 0:\n",
    "                return 1\n",
    "            elif S[i-1] == 'D':\n",
    "                return (dp(i, j+1) + dp(i-1, j)) % MOD\n",
    "            else:\n",
    "                return (dp(i, j-1) + dp(i-1, j-1)) % MOD\n",
    "\n",
    "        return sum(dp(N, j) for j in range(N+1)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPermsDISequence(self, s: str) -> int:\n",
    "        M = 10**9+7\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def f(i, low, high):\n",
    "        # perm of [0, n-i] for s[i:], valid first digit in [low, high]\n",
    "            if low > high or low < 0 or high > n-i:\n",
    "                return 0\n",
    "            if i == n:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            for x in range(low, high+1):\n",
    "                if s[i] == 'I': # [x+1, n-i] -> [x, n-i-1]\n",
    "                    ans += f(i+1, x, n-i-1)\n",
    "                else:\n",
    "                    ans += f(i+1, 0, x-1)\n",
    "            return ans % M\n",
    "        \n",
    "        return f(0, 0, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def numPermsDISequence(self, S):\n",
    "        MOD = 10**9 + 7\n",
    "        N = len(S)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(i, j):\n",
    "            # How many ways to place P_i with relative rank j?\n",
    "            if i == 0:\n",
    "                return 1\n",
    "            elif S[i-1] == 'D':\n",
    "                return sum(dp(i-1, k) for k in range(j, i)) % MOD\n",
    "            else:\n",
    "                return sum(dp(i-1, k) for k in range(j)) % MOD\n",
    "\n",
    "        return sum(dp(N, j) for j in range(N+1)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPermsDISequence(self, s: str) -> int:\n",
    "        M = 10**9+7\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def f(i, low, high):\n",
    "        # perm of [0, n-i] for s[i:], valid first digit in [low, high]\n",
    "            if low > high or low < 0 or high > n-i:\n",
    "                return 0\n",
    "            if i == n:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            for x in range(low, high+1):\n",
    "                if s[i] == 'I': # [x+1, n-i] -> [x, n-i-1]\n",
    "                    ans += f(i+1, x, n-i-1)\n",
    "                else:\n",
    "                    ans += f(i+1, 0, x-1)\n",
    "            return ans % M\n",
    "        \n",
    "        return f(0, 0, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPermsDISequence(self, s: str) -> int:\n",
    "        n = len(s) + 1\n",
    "        dp = [[0] * (n) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[0][i] = 1\n",
    "        for i in range(1, n):\n",
    "            for j in range(n - i):\n",
    "                if s[i - 1] == \"D\":\n",
    "                    for k in range(j + 1, n - i + 1):\n",
    "                        dp[i][j] += dp[i - 1][k]\n",
    "                else:\n",
    "                    for k in range(j + 1):\n",
    "                        dp[i][j] += dp[i - 1][k]\n",
    "        print(dp)\n",
    "        mod = 10 ** 9 + 7\n",
    "        return sum([dp[-1][i] % mod for i in range(n)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPermsDISequence(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def dfs(a, b):\n",
    "            if a == b == 0:\n",
    "                return 1\n",
    "            res = 0\n",
    "            if s[n - a - b] == 'D':\n",
    "                for i in range(a):\n",
    "                    res += dfs(i, b + a - i - 1)\n",
    "            else:\n",
    "                for i in range(b):\n",
    "                    res += dfs(a + b - i - 1, i)\n",
    "            return res\n",
    "        return sum(dfs(i, n - i) for i in range(n + 1)) % (10**9 + 7)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
